package com.practice.niuke.new_direct_practice.class12;

/**
 * 添加最少字符使字符串整体都是回文字符串
 * 给定一个字符串 str，如果可以在 str 的任意位置添加字符，请返回在添加字符最少
 * 的情况 下，让 str 整体都是回文字符串的一种结果。
 * 【举例】
 * str="ABA"。str 本身就是回文串，不需要添加字符，所以返回"ABA"。 str="AB"。可
 * 以在'A'之前添加'B'，使 str 整体都是回文串，故可以返回"BAB"。也可以在 'B' 之
 * 后添加'A'，使 str 整体都是回文串，故也可以返回"ABA"。总之，只要添加的字符数
 * 最少，返 回其中一种结果即可。
 * 进阶问题：（剥洋葱）
 * 给定一个字符串 str，再给定 str 的最长回文子序列字符串 strlps，请返回在添加
 * 字符最 少的情况下，让 str 整体都是回文字符串的一种结果。进阶问题比原问题多
 * 了一个参数， 请做到时间复杂度比原问题的实现低。
 */
public class Code04_PalindromeMinAdd {

    public static String getPalindrome1(String str) {
        if (str == null || str.length() < 2) {
            return str;
        }
        char[] chas = str.toCharArray();
        int[][] dp = getDP(chas);
        char[] res = new char[chas.length + dp[0][chas.length - 1]];
        int i = 0;
        int j = chas.length - 1;
        int resl = 0;
        int resr = res.length - 1;
        while (i <= j) {
            if (chas[i] == chas[j]) {
                res[resl++] = chas[i++];
                res[resr--] = chas[j--];
            } else if (dp[i][j - 1] < dp[i + 1][j]) {
                res[resl++] = chas[j];
                res[resr--] = chas[j--];
            } else {
                res[resl++] = chas[i];
                res[resr--] = chas[i++];
            }
        }
        return String.valueOf(res);
    }

    public static int[][] getDP(char[] str) {
        int[][] dp = new int[str.length][str.length];
        for (int j = 1; j < str.length; j++) {
            dp[j - 1][j] = str[j - 1] == str[j] ? 0 : 1;
            for (int i = j - 2; i > -1; i--) {
                if (str[i] == str[j]) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp;
    }

    public static void main(String[] args) {
        String str = "AB1CD2EFG3H43IJK2L1MN";
        System.out.println(getPalindrome1(str));
    }

}
